package org.company.earth.arithmetic;

import java.util.List;

/**
 * 快速排序，递归的概念，
 * 左边的元素小于p，右边的元素大于p
 * @author hucw
 *
 * @param <T>
 */
public class QuickSort<T> extends BaseSort<T> {

    @Override
    public void sort(List<T> list) {
        this.quickSort(list, 0, list.size()-1);
    }
    
    public void quickSort(List<T> list,int low,int high) {
        //递归结束条件
        if(low >= high) {
            return;
        }
        int privo = this.partition(list, low, high);
        this.quickSort(list, low, privo-1);
        this.quickSort(list, privo+1, high);
    }
    
    private Integer partition(List<T> list,Integer low,Integer high) {
        int privo = low;
        T t = list.get(privo);
        while(low < high) {
            while(low < high) {
                if(this.gt(t,list.get(high))) {
                    this.swap(list, low, high);
                    low++;
                    break;
                }
                high--;
            }
            while(low > high) {
                if(this.gt(list.get(low), t)) {
                    this.swap(list, low, high);
                    high--;
                    break;
                }
                low++;
            }
        }
        privo = low;
        list.set(privo, t);
        return privo;
    }
}
